package cn.yuemouren.suanfa;

/**
 * @Author: Timi
 * @Description: 快速排序
 * @Date: 2020/7/23 13:49
 */
public class QuickSort {

    public static void main(String[] args) {
        //int[] arr = {1,7,2,4,5,4,8,9,15,9};
        int[] arr = {12,20,5,16,15,1,30,45};
        sort(arr,0,arr.length-1);
        for (int i : arr)
            System.out.print(i+",");
        System.out.println("-------------");
    }

    private static void sort(int[] arr,int low,int high){
        int start = low;
        int end = high;
        int key = arr[low];

        while(start < end){
            //从后往前遍历
            while (start < end && arr[end] >= key)
                //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
                end--;
            if(arr[end] < key){
                swap(arr,end,start);
            }

            //从前往后
            while (start < end && arr[start] <= key)
                //如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
                start++;
            if(arr[start] > key){
                swap(arr,start,end);
            }
            //此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的
            //值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
        }

        //递归调用排序关键词左右的顺序
        if(start > low)
            sort(arr,low,start-1);
        if(end < high)
            sort(arr,end + 1,high);
    }

    private static void swap(int[] arr,int i,int j){
        int i1 = arr[i];
        arr[i] = arr[j];
        arr[j] = i1;
    }
}

/**
 *  public static void main(String[] args) {
 *
 *     }
 *
 *     private static void sort(int[] arr){
 *
 *     }
 */
